#pragma once
#include <iostream>
using namespace std;
class Solution {
public:

    void dfs(vector<string>& ret, int n, int left_num, int right_num, string str)
    {
        if(left_num == n && right_num == n)
        {
            ret.push_back(str);
            return;            
        }

        if(left_num < n)
        {
            dfs(ret, n, left_num + 1, right_num, str + '(');
        }

        if(right_num < left_num && right_num < n)
        {
            dfs(ret, n, left_num, right_num + 1, str + ')');
        }
    }


    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        dfs(ret, n, 0, 0, "");
        return ret;
    }
};
